package com.fmm.hard;

import java.util.*;

public class MapBestPath {

    /**
     * 一共有 n 个节点，编号为 0 到 n-1
     * edges[i] = {m, n, k} 表示第 i 条边连通着节点 m 和 n，距离为 k
     * start 和 end 分别是起点和终点的节点编号
     * 求出最短路径长度，如果无法到达则返回 -1
     * */
    public static int calculateBastPath(int n, int[][] edges, int start, int end) {
        // 通过边构建图结构，方便后面使用
        Map<Integer, List<Edge>> graph = buildGraph(edges);
        // 初始化各节点到开始节点的距离，除了开始节点本身，其他节点到开始节点都是无穷大
        // distance 为待处理的节点
        DistanceToStart[] distance = new DistanceToStart[n];
        for (int i = 0; i < n; i++) {
            if (i == start) {
                // 起点到它自身距离为 0
                distance[i] = new DistanceToStart(i, 0);
            } else {
                distance[i] = new DistanceToStart(i, Integer.MAX_VALUE);
            }
        }
        // 从待处理节点集合中获取距离开始节点最近的节点
        DistanceToStart minNode;
        while((minNode = pollMinNode(distance)) != null) {
            // 如果获取到的节点就是终点，表示已经计算到了要的结果，直接返回即可
            // 获取到的节点需要变绿
            if (minNode.getNodeIndex() == end) {
                return minNode.getDistance();
            }
            // 从图中获取到该节点的子节点
            List<Edge> subEdges = graph.get(minNode.getNodeIndex());
            for (Edge edge : subEdges) {
                // 更新这些子节点到开始节点的距离
                distance[edge.to()].updateDistance(
                        Math.min(distance[edge.to()].getDistance(), minNode.getDistance() + edge.distance()));
            }
        }
        // 全部循环完成后，如果终点的到开始节点的距离为无穷大，表示不可达，返回 -1，可达返回计算出的距离
        return distance[end].getDistance() == Integer.MAX_VALUE ? -1 : distance[end].getDistance();
    }

    private static DistanceToStart pollMinNode(DistanceToStart[] distance) {
        DistanceToStart result = Arrays.stream(distance).filter(dt -> !dt.isGreen()).sorted(
                Comparator.comparingInt(DistanceToStart::getDistance)).findFirst().get();
        result.setGreen();
        return result;
    }

    private static Map<Integer, List<Edge>> buildGraph(int[][] edges) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int distance = edge[2];
            graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(from, to, distance));
        }
        return graph;
    }

    private static class DistanceToStart {
        private int nodeIndex;
        private int distance;
        private boolean green;

        public DistanceToStart(int nodeIndex, int distance) {
            this.nodeIndex = nodeIndex;
            this.distance = distance;
            this.green = false;
        }

        public boolean isGreen() {
            return green;
        }

        public int getNodeIndex() {
            return nodeIndex;
        }

        public int getDistance() {
            return distance;
        }

        public void setGreen() {
            this.green = true;
        }
        void updateDistance(int distance) {
            this.distance = distance;
        }
    }
    private record Edge(int from, int to, int distance) {
    }

    public static void main(String[] args) {
        int n = 8;
        int[][] edges = {
                {0, 1, 5},
                {1, 2, 2},
                {2, 3, 4},
                {3, 4, 1},
                {1, 4, 1},
                {0, 5, 3},
                {5, 4, 2},
                {5, 6, 7},
                {5, 7, 2},
                {7, 6, 3},
                {4, 7, 1}
        };
        int start = 0;
        int end = 6;
        System.out.println(calculateBastPath(n, edges, start, end));
    }
}
